#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <assert.h>
#include "htable.h"
#include "plex.h"

typedef struct hitem hitem_t;
struct hitem
{
    hitem_t*        next;
    unsigned int    hash; //1.speed key compare; 2. easy array's expand
    const void*     key;
    int             ksize;
    void*           val;
};

struct htable
{
    hitem_t**       arr;    //
    size_t          size;   //array size
    size_t          count;  //item count

    ht_hashfunc_t   f_hash;
    int             expand; //htable is expand,default 0
    plex_t*         plex;   //item's memory mgr
};

static unsigned int ht_hashfunc(const void *char_key, int *klen)
{
    unsigned int hash = 0;
    const unsigned char *key = (const unsigned char *)char_key;
    const unsigned char *p;
    int i;
    if (*klen == -1)
    {
        for (p = key; *p; p++)
        {
            hash = hash * 33 + *p;
        }
        *klen = p - key;
    }
    else
    {
        for (p = key, i = *klen; i; i--, p++)
        {
            hash = hash * 33 + *p;
        }
    }

    return hash;
}

#define HTABLE_INIT_SIZE  15

htable_t* htable_create(size_t nel)
{
    htable_t* me = calloc(1, sizeof(*me));
    if (!me)
    {
        return 0;
    }
    me->f_hash = ht_hashfunc;
    me->size = (nel>HTABLE_INIT_SIZE)? nel : HTABLE_INIT_SIZE;
    me->arr = calloc(me->size, sizeof(hitem_t*));
    if (!me->arr)
    {
        free(me);
        return 0;
    }
    return me;
}

void htable_set_plex(htable_t* me, unsigned int nmemb)
{
    assert(me);
    if (!me->plex)
    {
        me->plex = plex_new(nmemb, sizeof(hitem_t));
    }
}

void htable_enable_expand(htable_t* me, int enable)
{
    assert(me);
    me->expand = enable;
}

void htable_free(htable_t* me)
{
    assert(me && me->arr);
    htable_clear(me);
    if (me->plex)
    {
        plex_delete(me->plex);
    }
    free(me->arr);
    free(me);
}

size_t htable_count(htable_t* me)
{
    return me->count;
}

static ht_action_e iter_clear(void* ctx, const void* key, int ksize, void* val)
{
    return HT_CONTINUE|HT_REMOVE;
}

void htable_clear(htable_t* me)
{
    htable_iterate(me, iter_clear, 0);
    assert(me->count == 0);
}

static inline hitem_t* find_item(hitem_t* head, hitem_t** pprev, unsigned int hash, const void* key, int ksize)
{
    hitem_t* item = head;
    if (pprev)
        *pprev = head;
    while (item)
    {
        if ((item->hash == hash)
                && (item->ksize == ksize)
                && (0 == memcmp(key, item->key, ksize))
           )
        {
            return item;
        }

        //next
        if (pprev)
            *pprev = item;
        item = item->next;
    }
    return 0;
}

static void htable_expand(htable_t* me)
{
    size_t newsize = me->size*2 + 1;
    hitem_t** newarr = calloc(newsize, sizeof(hitem_t*));
    size_t i = 0;

    if (!newarr)
        return;

    for (i=0; i<me->size; i++)
    {
        hitem_t* prev = me->arr[i];
        hitem_t* item = me->arr[i];
        while (item)
        {
            size_t newidx = item->hash % newsize;
            if (newidx != i)
            {
                hitem_t* newitem = item;
                //remove from current
                if (me->arr[i] == item)
                    me->arr[i] = 0;
                else
                    prev->next = item->next;
                item = item->next;

                //add new pos
                newitem->next = newarr[newidx];
                newarr[newidx] = newitem;

                continue;
            }

            //next
            prev = item;
            item = item->next;
        }
    }
    
    //fix
    free(me->arr);
    me->arr = newarr;
    me->size = newsize;
}

int htable_set(htable_t* me, const void* key, int ksize, void* val)
{
    unsigned int hash = 0;
    hitem_t* item = 0;
    int idx = 0;

    assert(me && key && ksize>=-1);

    //find
    hash = me->f_hash(key, &ksize);
    idx = hash % me->size;
    item = find_item(me->arr[idx], 0, hash, key, ksize);
    if (item)
    {
        item->val = val;
        return 0;
    }

    //item alloc
    item = ITEM_MALLOC(me->plex, sizeof(*item));
    if (!item)
        return -1;
    item->hash = hash;
    item->key = key;
    item->ksize = ksize;
    item->val = val;

    //join the list
    item->next = me->arr[idx];
    me->arr[idx] = item;

    me->count++;
    if (me->count > me->size && me->expand)
    {
        htable_expand(me);
    }
    return 0;
}

int htable_add(htable_t* me, const void* key, int ksize, void* val)
{
    unsigned int hash = 0;
    hitem_t* item = 0;
    int idx = 0;

    assert(me && key && ksize>=-1);

    //find
    hash = me->f_hash(key, &ksize);
    idx = hash % me->size;
    item = find_item(me->arr[idx], 0, hash, key, ksize);
    if (item)
    {
        errno = EEXIST;
        return -1;
    }

    //item alloc
    item = ITEM_MALLOC(me->plex, sizeof(*item));
    if (!item)
        return -1;
    item->hash = hash;
    item->key = key;
    item->ksize = ksize;
    item->val = val;

    //join the list
    item->next = me->arr[idx];
    me->arr[idx] = item;

    me->count++;
    if (me->count > me->size && me->expand)
    {
        htable_expand(me);
    }
    return 0;
}

void* htable_get(htable_t* me, const void* key, int ksize)
{
    unsigned int hash = 0;
    hitem_t* item = 0;

    assert(me && key && ksize>=-1);

    //find
    hash = me->f_hash(key, &ksize);
    item = find_item(me->arr[hash % me->size], 0, hash, key, ksize);

    return item? item->val : 0;
}

void* htable_rm(htable_t* me, const void* key, int ksize)
{
    unsigned int hash = 0;
    int idx = 0;
    hitem_t* item = 0;
    hitem_t* prev = 0;

    assert(me && key && ksize>=-1);

    //find
    hash = me->f_hash(key, &ksize);
    idx = hash % me->size;
    item = find_item(me->arr[idx], &prev, hash, key, ksize);
    if (item)
    {
        void* val = item->val;
        if (me->arr[idx] == item)
            me->arr[idx] = 0;
        else
            prev->next = item->next;
        ITEM_FREE(me->plex, item);
        me->count--;
        return val;
    }
    return 0;
}

void htable_set_hash(htable_t* me, ht_hashfunc_t func)
{
    assert(me && func);
    me->f_hash = func;
}

void htable_iterate(htable_t* me, ht_iterfunc_t iter, void* ctx)
{
    int i = 0;

    assert(me && iter);
    for (i=0; i<me->size; i++)
    {
        hitem_t* prev = me->arr[i];
        hitem_t* item = me->arr[i];
        while (item)
        {
            ht_action_e action = iter(ctx, item->key, item->ksize, item->val);
            if (action & HT_REMOVE)
            {
                hitem_t* old = item;

                //remove from curpos
                if (me->arr[i] == item)
                    me->arr[i] = 0;
                else
                    prev->next = item->next;
                item = item->next;

                //free it
                ITEM_FREE(me->plex, old);
                me->count--;
                if (action & HT_CONTINUE)
                    continue;
                assert(action & HT_BREAK);
                return;
            }
            else if (action & HT_BREAK)
            {
                return;
            }
            else
            {
                assert(action & HT_CONTINUE);
            }

            //next
            prev = item;
            item = item->next;
        }
    }
}

void htable_dump(htable_t* me, FILE* to)
{
    size_t i = 0;
    assert(me && to);
    fprintf(to, "<--! htable dump start\n");
    fprintf(to, "ht size=%d count=%d\n", me->size, me->count);
    if (me->plex)
    {
        fprintf(to, "plex nmemb=%d, size=%d\n", me->plex->nmemb, me->plex->size);
#ifdef PLEX_DEBUG
        fprintf(to, "plex count_alloc=%d count_free=%d\n", me->plex->count_alloc, me->plex->count_free);
#endif 
    }
    
    for (i=0; i<me->size; i++)
    {
        hitem_t* item = me->arr[i];
        fprintf(to, "[%d] ", i);
        while(item)
        {
            fprintf(to, "(h=%d, s=%d) ", item->hash, item->ksize);
            item = item->next;
        }
        fprintf(to, "\n");
    }
    fprintf(to, "htable dump end -->\n\n");
}

